package J2_5;

public class test {


    private class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

    //给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历，
    //inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
    int index;
    public TreeNode buildTree1(int[] preorder, int[] inorder) {
        return creatTree1(preorder,inorder,0,inorder.length - 1);
    }

    public TreeNode creatTree1(int[] preorder, int[] inorder, int preIndex, int endIndex) {
        if(preIndex > endIndex) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[index]);
        int inIndex = searchIndex(inorder,preorder[index]);
        index++;
        root.left = creatTree1(preorder,inorder,preIndex,inIndex-1);
        root.right = creatTree1(preorder,inorder,inIndex+1,endIndex);
        return root;

    }

    private int searchIndex(int[] inorder,int a) {
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == a) {
                return i;
            }
        }
        return -1;
    }

    //给定两个整数数组 inorder 和 postorder ，
    // 其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
    int index2 = 1;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return creatTree(postorder,inorder,0,inorder.length-1);
    }
    public TreeNode creatTree(int[] preorder, int[] inorder, int preIndex, int endIndex) {
        if(preIndex > endIndex) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[preorder.length-index2]);
        int inIndex = searchIndex(inorder,preorder[preorder.length-index2]);
        index2++;
        root.right = creatTree(preorder,inorder,inIndex+1,endIndex);
        root.left = creatTree(preorder,inorder,preIndex,inIndex-1);
        return root;

    }


    //给你二叉树的根节点 root ，请你采用前序遍历的方式，
    // 将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
    //
    //空节点使用一对空括号对 "()" 表示，
    // 转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
    public String tree2str(TreeNode root) {

        StringBuilder str = new StringBuilder();

        creatStr(root,str);

        return str.toString();

    }
    private void creatStr(TreeNode root,StringBuilder str) {
        if (root == null) {
            return;
        }
        str.append(root.val);

        if (root.left != null) {
            str.append("(");
            creatStr(root.left,str);
            str.append(")");
            if (root.right != null) {
                str.append("(");
                creatStr(root.right,str);
                str.append(")");
            }
        } else if (root.right!=null) {
            str.append("()");
            str.append("(");
            creatStr(root.right,str);
            str.append(")");
        }

    }
}
